This invention relates generally to the encoding of data for transmission and storage, more particularly the invention relates to the encoding and decoding of Reed-Solomon (RS) codes.
The trend towards higher densities and data rates in magnetic data recording has required error control coding and modulation techniques. Error detection and correction coding can use a polynomial with binary coefficients to represent a sequence of binary bits and with a plurality of check bits determined by a coding process which requires that every code word be divisible by a preselected polynomial with zero remainder. A plurality of cyclic codes can be interleaved to form a cyclic code for further error reduction. Further, the binary base field can be extended to a finite field of 2.sup.m elements, known as a Galois field GF (2.sup.m) in which all elements are represented by m-bit binary symbols.
The Reed-Solomon (RS) code is based on an extension of the concepts of cyclic codes in an extended binary field GF (2.sup.m). All processing of these polynomials is done using sum and product operations defined in the extension field GF (2.sup.m). In this system, the generator G(z), the information sequence M(z), the remainder C(z), and the code word W(z) are all polynomials whose coefficients are elements in GF(2.sup.m) in the form of m-bit bytes.
An (n,k) Reed-Solomon (RS) code over the finite field FG(2.sup.m) has k message symbols and r=n-k redundant check symbols, where each symbol is m bits wide and n=r+k=code length in symbols. The check symbols C.sub.r-1, C.sub.r-2 . . . , C.sub.1, C.sub.0 are computed from the message symbols M.sub.k-1, M.sub.k-2 . . . , M.sub.1, M.sub.0 using the formula EQU C(z)=M(z)z.sup.r modulo G(z)
where C(z)=C.sub.r-1 z.sup.r-1 +C.sub.r-2 z.sup.r-2 + . . . +C.sub.1 z+C.sub.0 is the check polynomial, M(z)=M.sub.k-1 z.sup.k-2 + . . . +M.sub.1 z+M.sub.0 is the message polynomial and G(z)=z.sup.r +G.sub.r-1 Z.sup.r-1 +G.sub.r-2 z.sup.r-2 +. . .+G.sub.1 z+G.sub.0 is the generator polynomial of the RS code. C(z) is the remainder when M(z)z.sup.r is divided by G(z).
The conventional parallel implementation of an RS encoder is shown in FIG. 1 in which a message and the content of a register are summed and applied through a MUX 10 to a plurality of multipliers 12 which multiply the sum by coefficients, G.sub.i, with the products added to contents of registers 14 in adders 16 and then sorted in other registers 14.
In this parallel approach, a message symbol is input every clock cycle, and r finite field multiplications (by the r constant coefficients, G.sub.i, of the generator polynomial) and r finite field additions are performed every clock cycle. The message select signal is high when message symbols are being input and low when the redundant check symbols are being output. The other signals in FIG. 1 are all m bits wide where m is the number of bits per symbol. In this approach, r constant finite field multipliers 12, r finite field adders 16, and r symbol registers 14 are needed.
Copending Ser. No. 07/829,655, supra., discloses an encoder including a single multiplexer and a single adder for obtaining the quotient or redundant check signals of the polynomial division, depending on whether all message symbols have been input to the encoder. The intermediate results of the computation are fed back to the discrete time delay line, controlled by a feedback control signal. The discrete time delay line delays the data by r-1 clock cycles. The output of the delay line if controlled by a sync signal which suitably initializes the delay line at the beginning of a new message block. The encoder replaces the r constant multipliers in the conventional parallel approach by a single general multiplier. all memory elements are lumped together in the single delay line. Since the delay line is implemented with a random access memory together with simple control logic, a significant reduction of hardware is realized due to the density of the RAM cells compared with registers as used in the conventional parallel encoder.
The present invention is directed to a Reed-Solomon decoder and particularly to a power sum computation unit in the decoder which uses a discrete time delay for serial computations.